package pro1.t167;

/**
 * @Author xingyu Xue
 * @Date 2024/2/1 12:28
 *
 * 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
 * 如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
 *
 * 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
 *
 * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
 * 你所设计的解决方案必须只使用常量级的额外空间。
 *
 *
 *这个题比较特殊，只有唯一的答案
 *
 */
public class 两数之和 {
    /**
     * 双指针法，一个在最左边指，一个在最右边指。
     * 且要用到数组拍好序的特性
     * @param numbers
     * @param target
     * @return
     *
     *
     * 自己写的，跑通了！！！
     * 但是超时了
     */
    public static int[] twoSum(int[] numbers, int target) {
        int[] result=new int[2];
        int n= numbers.length;

        for (int i = 0; i < n; i++) {// i左指针、j右指针

            for (int j = n-1; j>i ; j--) {
                if (numbers[i]+numbers[j]==target) {
                    result[0]=i+1;
                    result[1]=j+1;
                }
                /**
                 * 我这种写法，就是没理解到 排序+双指针 灵魂。
                 * 当==target后，第二层for循环明显是多余的，因为你第一个值和最后一个值等于target了，那么最后一个值前面的值，
                 * 都比最后一个值小，加起来怎么可能等于target???明显不惜要去for循环了
                 */
            }

        }
        return result;

    }

    /**
     * 同样是双指针算法
     * 这种写法就没有超时，看来还是双指针没用到位。
     * @param numbers
     * @param target
     * @return
     * O(N)
     */
    public  static int[] twoSum2(int[] numbers, int target) {
        int i = 0;   //左指针
        int j = numbers.length - 1;//右指针
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum < target) {
                i++;
            } else if (sum > target) {
                j--;
            } else {
                return new int[]{i+1, j+1};
            }
        }
        return new int[]{-1, -1};
    }


}
